package com.example.search;

import java.util.ArrayList;
import java.util.List;

class Block {
    int max;
    int start;

    public Block(int max, int start) {
        this.max = max;
        this.start = start;
    }
}

public class BlockSearch {

    public static void main(String[] args) {
        int[] arr = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48};
        int blockSize = 4;
        List<Block> indexTable = createIndexTable(arr, blockSize);
        int target = 24;
        int result = blockSearch(arr, indexTable, blockSize, target);
        if (result != -1) {
            System.out.println("元素" + target + "的位置是：" + result);
        } else {
            System.out.println("元素" + target + "不存在");
        }
    }

    // 创建索引表
    private static List<Block> createIndexTable(int[] arr, int blockSize) {
        List<Block> indexTable = new ArrayList<>();
        for (int i = 0; i < arr.length; i += blockSize) {
            int start = i;
            int end = Math.min(i + blockSize, arr.length);
            int max = findMax(arr, start, end);
            indexTable.add(new Block(max, start));
        }
        return indexTable;
    }

    // 查找块内最大值
    private static int findMax(int[] arr, int start, int end) {
        int max = arr[start];
        for (int i = start; i < end; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    // 分块查找
    private static int blockSearch(int[] arr, List<Block> indexTable, int blockSize, int target) {
        for (Block block : indexTable) {
            if (block.max >= target) {
                int start = block.start;
                int end = Math.min(start + blockSize, arr.length);
                for (int i = start; i < end; i++) {
                    if (arr[i] == target) {
                        return i;
                    }
                }
            }
        }
        return -1;
    }
}